package com.lmk.dsa.struct.heap;

import com.lmk.dsa.struct.commons.KvNode;

/**
 * 索引堆
 * @author LaoMake
 * @since 1.0
 */
public abstract class IndexHeap {

    /** 数据数组 */
    protected KvNode[] data;

    /** 索引数组 */
    protected int[] indexes;

    /** 反向查找索引，reverse[i]用于确定：索引i在indexes数组（堆）中的索引位置 */
    protected int[] reverse;

    /** 堆容量：静态数组的长度 */
    protected Integer capacity;

    /** 堆中数据节点的总数 */
    protected Integer size;

    /**
     * 对指定索引位置的元素进行上浮操作
     * @param childIndex
     */
    protected abstract void siftUp(int childIndex);

    /**
     * 对指定索引位置的元素进行下沉操作
     * @param parentIndex
     */
    protected abstract void siftDown(int parentIndex);

    public IndexHeap() {
        this(20);
    }

    public IndexHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.data = new KvNode[capacity];
        this.indexes = new int[capacity];
        this.reverse = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            reverse[i] = -1;
        }
    }

    public int size() {
        return this.size;
    }



    public <K extends Comparable<? super K>, V> void insert(int index, K key) {
        insertNode(index, new KvNode(key, null));
    }

    public <K extends Comparable<? super K>, V> void insert(int index, K key, V value) {
        insertNode(index, new KvNode(key, value));
    }

    public void insertNode(int index, KvNode node) {
        // 数组已满，进行扩容操作
        if(size == data.length){
            grow();
        }

        data[index] = node;
        indexes[size] = index;
        reverse[index] = size;
        siftUp(size);
        size++;
    }

    /**
     * 判断是否包含某个Key
     * @param key
     * @param <K>
     * @return
     */
    public <K extends Comparable<? super K>> boolean containsKey(K key) {
        boolean contains = false;
        KvNode node;
        for (int i = 0; i < size; i++) {
            if(data[i].key.compareTo(key) == 0){
                contains = true;
                break;
            }
        }
        return contains;
    }

    /**
     * 判断当前堆中是否包含某个索引
     * @param index
     * @return
     */
    public boolean containsIndex(int index) {
        assert index >= 0 && index < capacity;
        return reverse[index] != -1;
    }

    public <K extends Comparable<? super K>, V> void change(int index, K key) {
        change(index, key, null);
    }

    /**
     * 修改节点值
     * @param index
     * @param key
     * @param value
     * @param <K>
     * @param <V>
     */
    public <K extends Comparable<? super K>, V> void change(int index, K key, V value) {
        KvNode node = data[index];
        node.key = key;
        node.value = value;

        // 寻找该节点在堆中的索引
        int heapIndex = reverse[index];
        // 调整、保持堆特性
        siftUp(heapIndex);
        siftDown(heapIndex);
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public KvNode pool() {
        assert size > 0;

        KvNode node = data[indexes[0]];
        indexes[0] = indexes[size - 1];
        reverse[indexes[0]] = 0; // 同步反向查找索引
        reverse[indexes[size - 1]] = -1; // 代表该元素已删除

        siftDown(0);
        size--;
        return node;
    }

    /**
     * 获取堆顶元素索引
     * @return
     */
    public int poolIndex() {
        assert size > 0;

        int index = indexes[0];
        indexes[0] = indexes[size - 1];
        reverse[indexes[0]] = 0; // 同步反向查找索引
        reverse[indexes[size - 1]] = -1; // 代表该元素已删除

        siftDown(0);
        size--;
        return index;
    }

    /**
     * 根据索引获取节点信息
     * @param index
     * @return
     */
    public KvNode getNode(int index){
        return data[index];
    }

    /**
     * 根据孩子节点的索引获取父节点索引
     * @param child
     * @return
     */
    protected int parent(int child){
        return (child - 1) / 2;
    }

    /**
     * 根据父节点的索引获取左孩子的索引
     * @param parent
     * @return
     */
    protected int leftChild(int parent){
        return parent * 2 + 1;
    }

    /**
     * 根据父节点的索引获取右孩子的索引
     * @param parent
     * @return
     */
    protected int rightChild(int parent){
        return parent * 2 + 2;
    }

    /**
     * 交换索引数组中两个位置的元素
     * @param i
     * @param j
     */
    protected void swapIndexes(int i, int j){
        int index = indexes[i];
        indexes[i] = indexes[j];
        indexes[j] = index;
    }

    /**
     * 数组扩容，默认增长为原来的1.5倍
     */
    protected void grow(){
        int len = data.length;
        len += len >> 1;
        capacity = len;
        KvNode[] newNodes = new KvNode[capacity];
        System.arraycopy(data, 0, newNodes, 0, size);

        int[] newIndexes = new int[capacity];
        System.arraycopy(indexes, 0, newIndexes, 0, size);

        this.data = newNodes;
        this.indexes = newIndexes;
    }

    /**
     * 转换为数组
     * @return
     */
    public Object[] toArray(){
        Object[] result = new Object[size];
        for (int i = 0; i < size; i++) {
            result[i] = data[indexes[i]];
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[indexes[i]]).append(", ");
        }

        if (size > 0){
            sb.delete(sb.length() - 2, sb.length());
        }
        sb.append("]");
        return sb.toString();
    }

    /**
     * 原地堆排序
     * @return
     */
    public KvNode[] sort(){
        return null;
    }
}
